package day08;

/**
 * 给定一个正整数数组 nums和一个整数 k，返回 num中 「好子数组」的数目。
 *
 * 如果 nums的某个子数组中不同整数的个数恰好为 k，则称 nums的这个连续、不一定不同的子数组为 「好子数组 」。
 *
 * 例如，[1,2,3,1,2] 中有3个不同的整数：1，2，以及3。
 * 子数组 是数组的 连续 部分。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,1,2,3], k = 2
 * 输出：7
 * 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
 * 示例 2：
 *
 * 输入：nums = [1,2,1,3,4], k = 3
 * 输出：3
 * 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
 *
 *
 */
public class Solution7 {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return slideWindow(nums,k)-slideWindow(nums,k-1);
    }
    public int slideWindow(int []nums,int k){
        int right = 0,left = 0,len = nums.length;
        int ans=0,count=0;
        int []frq = new int[len+1];
        while (right<len){
            if(frq[nums[right]]==0){
                count++;
            }
            frq[nums[right]]++;
            right++;
            while (count>k){
                frq[nums[left]]--;
                if(frq[nums[left]]==0){
                    count--;
                }
                left++;
            }
            ans+=right-left;
        }
        return ans;
    }
}
